package ch10;

public class Ch10_5 {
	public static int find(String[] seq, String key) {
		int l = 0, r = seq.length - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			int gap = 0;
			while (gap + mid <= r && seq[gap + mid].isEmpty()) {
				gap++;
			}
			if (gap + mid == seq.length) {
				r = mid - 1;
			} else {
				int compare = seq[gap + mid].compareTo(key);
				if (compare == 0) {
					return gap + mid;
				} else if (compare > 0) {
					r = mid - 1;
				} else {
					l = mid + gap + 1;
				}
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		String[] seq = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
		String key = "";
		System.out.println(find(seq, key));
	}
}
